﻿// 2507. 使用质因数之和替换后可以取到的最小值.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


using namespace std;
/*
https://leetcode.cn/problems/smallest-value-after-replacing-with-sum-of-prime-factors/description/
给你一个正整数 n 。

请你将 n 的值替换为 n 的 质因数 之和，重复这一过程。

注意，如果 n 能够被某个质因数多次整除，则在求和时，应当包含这个质因数同样次数。
返回 n 可以取到的最小值。


示例 1：
输入：n = 15
输出：5
解释：最开始，n = 15 。
15 = 3 * 5 ，所以 n 替换为 3 + 5 = 8 。
8 = 2 * 2 * 2 ，所以 n 替换为 2 + 2 + 2 = 6 。
6 = 2 * 3 ，所以 n 替换为 2 + 3 = 5 。
5 是 n 可以取到的最小值。


示例 2：
输入：n = 3
输出：3
解释：最开始，n = 3 。
3 是 n 可以取到的最小值。


提示：
2 <= n <= 105
*/


class Solution {
public:
    
    int smallestValue(int n) {
        int pre = 0;
        while (pre != n) {
            pre = n; int sum = 0;
            for (int i = 2; i <= n / i; i++) {
                while (n % i == 0) {
                    n = n / i;
                    sum += i;
                }
            }
            if (n > 1) sum += n;
            n = sum;
        }
        return n;
    }
};



int main()
{
    Solution s;
    cout << s.smallestValue(15);

    return 0;
}

 